package leetcode.weekly.week290;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution6 implements IDebug {

	public int[] countRectangles(int[][] rectangles, int[][] points) {
//		Set<Integer> set = new HashSet<Integer>();
//		for (int i = 0; i < rectangles.length; i++) {
//			set.add(rectangles[i][0]);
//			set.add(rectangles[i][1]);
//		}
//		for (int i = 0; i < points.length; i++) {
//			set.add(points[i][0]);
//			set.add(points[i][1]);
//		}
//		List<Integer> nums = new ArrayList<>(set);
//		Collections.sort(nums);
//		Map<Integer, Integer> idx = new HashMap<>();
//		for (int i = 0; i < nums.size(); i++) {
//			idx.put(nums.get(i), i);
//		}
//		for (int i = 0; i < rectangles.length; i++) {
//			rectangles[i][0] = idx.get(rectangles[i][0]);
//			rectangles[i][1] = idx.get(rectangles[i][1]);
//		}
//		for (int i = 0; i < points.length; i++) {
//			points[i][0] = idx.get(points[i][0]);
//			points[i][1] = idx.get(points[i][1]);
//		}
		Arrays.sort(rectangles, (a, b) -> a[1] - b[1]);
		int[] ans = new int[points.length];
		for (int i = 0; i < points.length; i++) {
			int[] point = points[i];
			int x = point[0], y = point[1];
			int bx = this.findx(rectangles, y);
			int by = this.findy1(rectangles, x, bx);
			ans[i] = by;
		}
		return ans;
	}

	private int findy1(int[][] rectangles, int y, int bx) {
		if (bx == -1) {
			return 0;
		}
		int ans = 0;
		for (int i = bx; i < rectangles.length; i++) {
			if (rectangles[i][0] >= y) {
				ans++;
			}
		}
		return ans;
	}

	private int findx(int[][] rectangles, int x) {
		int l = 0, r = rectangles.length - 1;
		int ans = -1;
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			if (rectangles[mid][1] >= x) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
		int[] ans = H.str2array3("[2,1]");
		H.compare(ans, this.countRectangles(H.str2array1("[[1,2],[2,3],[2,5]]"), H.str2array1("[[2,1],[1,4]]")));

	}

	@Override
	public void debug3() {
		int[] ans = H.str2array3("[1,3]");
		H.compare(ans, this.countRectangles(H.str2array1("[[1,1],[2,2],[3,3]]"), H.str2array1("[[1,3],[1,1]]")));
	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
		int[] ans = H.str2array3("[5,0]");
		H.compare(ans,
				this.countRectangles(H.str2array1("[[4,7],[4,9],[8,5],[6,2],[6,4]]"), H.str2array1("[[4,2],[5,6]]")));
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub
		int[] ans = H.str2array3("[4]");
		H.compare(ans, this.countRectangles(H.str2array1("[[7,1],[2,6],[1,4],[5,2],[10,3],[2,4],[5,9]]"),
				H.str2array1("[[2,3]]")));
//		int[] ans = H.str2array3("[1,0,4,1,0,0,0,1]");
//		H.compare(ans,this.countRectangles(H.str2array1("[[7,1],[2,6],[1,4],[5,2],[10,3],[2,4],[5,9]]"), H.str2array1("[[10,3],[8,10],[2,3],[5,4],[8,5],[7,10],[6,6],[3,6]]")));

	}

	public static void main(String[] args) {
		Solution6 so = new Solution6();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

//	[[49,26],[7,80],[79,10],[57,23],[23,20],[24,82],[47,62],[55,93],[84,62],[67,22]]
//			[[65,31],[54,59],[57,46],[63,49],[87,93],[81,4],[23,50],[58,33],[100,39],[79,58],[89,25],[12,37],[83,68],[19,16],[22,44],[5,87],[33,82],[69,62],[67,29],[92,25],[51,98],[48,60],[62,87],[71,59],[99,81],[91,91],[26,83],[40,87],[28,42],[94,53],[80,24],[10,94],[16,1],[45,7],[50,39],[53,37],[76,50],[7,69],[1,81],[95,40],[48,73],[47,16],[38,5],[41,17],[24,37],[35,10],[25,92],[9,78],[66,97],[34,52],[28,45],[33,28],[55,48],[25,17],[14,24],[70,63],[6,47],[13,32],[64,36],[57,1],[37,62],[41,61],[56,77],[41,18],[69,43],[69,68],[24,11],[51,35],[5,86],[44,67],[98,21],[81,53],[78,69]]

}
